package com.pandy.code;

import java.util.Arrays;

/**
 * 二分法相关
 * 时间复杂度：O(logN)
 */
public class Code02_BinarySearch {

    /**
     * 获取局部最小值
     * 任意相邻2个数不相等
     *
     * 找出一个局部最小
     * 理解：什么是局部最小
     * arr[0] < arr[1] === arr[0]是一个局部最小
     * arr[n-1] < arr[n-2] === arr[n-1]是一个局部最小
     *
     * arr[k] < arr[k-1] && arr[k] < arr[k+1] === arr[k]也是一个局部最小
     *
     * 分析
     * arr[1] > arr[0]  下降趋势
     * arr[n-2] < arr[n-1] 上升趋势
     * 下贱趋势到上升趋势  中间肯定有一个局部最小的位置
     * @param arr
     * @return
     */
    public static int getLocalMinimum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        if(arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        int size = arr.length;
        if(arr[size - 1] < arr[size - 2]) {
            return size - 1;
        }

        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if(arr[mid -1] < arr[mid]){
                R = mid - 1;
            } else if(arr[mid + 1] < arr[mid]){
                L = mid + 1;
            } else {
                return mid;
            }
        }

        return L;
    }

    /**
     * 在一个有序数组中，找到>=某个数最左侧位置
     * @param arr
     * @param value
     * @return
     */
    public static int getLeftmostIndex(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 记录最左侧位置
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if(arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        return index;
    }

    /**
     * 在一个有序数组中，找某个数是否存在
     * @param arr
     * @param num
     * @return
     */
    public static boolean exist(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }

        int L = 0;
        int R = arr.length - 1;
        while (L < R) {
            int mid = L + ((R - L) >> 1);
            if(num > arr[mid]) {
                L = mid + 1;
            } else if(num < arr[mid]) {
                R = mid - 1;
            } else {
                return true;
            }
        }

        return arr[L] == num;
    }

    public static void print(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4,6,1,4,6,8,3,5,2,1,6};
        //Arrays.sort(arr);
        print(arr);
        System.out.println(getLocalMinimum(arr));
    }
}
